#!/usr/bin/env python
# coding: utf-8

"""
Created on 10/10/2011

@author: Rubén López
@author: Alfredo Campuzano
"""

from automata import DFA, NFA
from bnf import BNF

class DefinitionToRegex:
    """A syntax-directed translation scheme that translates a regular
    definition to its corresponding postfix regular expression.

    The input regular get_definition can have one ore more statements of the
    following form: 'name = expression;'. The 'name' can contain white
    spaces. The expression can use previously defined names within '['
    and ']'. For example:

    letter = a | b;
    digit = 0 | 1 | 2;
    id = [letter]([letter]|[digit])*

    or,

    letter a = a; letter b = b; digit = 0 | 1 | 2;
    id = [letter a]([letter b]|[digit])*

    Line returns ('\n') are ignored.

    A draw method is included to draw one nfa for each statement.
    """

    def __init__(self, regdef="", alphabet=[]):

        # Global variables
        self.regdef = regdef           # the input regular definition
        self.alphabet = alphabet[::]   # the alphabet
        self.reserved = "|.*+?()[]=;"  # reserved characters
        self.definitions = {}          # dict of form 'name -> (exp, def)'
        self.translation = ""          # final postfix regular expresion
        self.errors = []               # global error table

        # Local variables to parse one statement
        self.input = ""                # the input expersion to parse
        self.exp_output = ""           # postfix output with only terminals
        self.def_output = []           # postfix output with (non)terminals
        self.index = 0                 # index of next terminal in input
        self.lookahead = ""            # next terminal in input
        self.end_reached = False       # indicates if parse failed

    def traslate(self):
        """Executes the translation from the input regular defintion to an
        infix regular expression.
        """

        # remove special characters from alphabet
        if "ε" in self.alphabet:
            self.alphabet.remove("ε")
        if "" in self.alphabet:
            self.alphabet.remove("")

        # check if the alphabet is correct
        for char in self.reserved:
            if char in self.alphabet:
                self.errors.append("error in alphabet: char '" + char + \
                                   "' is reserved")
                return

        # initialize global variables
        self.errors = []
        self.end_reached = False
        self.definitions.clear()

        i = 0 # statement number
        for stmt in self.regdef.split(";"):
            if stmt != "":
                # check for error in statement
                name, sep, exp = stmt.strip().partition("=")
                if name == "" or sep == "" or exp == "":
                    self.errors.append("error: statement " + str(i) + \
                                       " is malformed.")
                    continue
                # check if the name is allready defined.
                name = name.strip()
                if name in self.definitions:
                    self.errors.append("error: '" + name + "' in statement " \
                                       + str(i) + " defined twice.")
                    continue
                # initialize temporal variables
                self.input = exp.strip()
                self.index = -1
                self.lookahead = self.next_terminal()
                self.exp_output = ""
                self.def_output = []
                # try to parse the next statement
                self.exp0()
                # check if parse failed
                if not self.end_reached == True:
                    self.errors.append("error: failed to parse statement" + \
                                       str(i) + ".")
                    continue
                # exp_output is the postfix notation with only terminals
                # (characters in the alphabet plus reserved characters) and
                # def_output is the postfix notation with terminals and
                # non-terminals (names of previous definitions)
                self.definitions[name] = (self.exp_output, self.def_output)
        # save the final exp_output as the final translation
        self.translation = self.exp_output
        return self.translation

    def next_terminal(self, ignore=True):
        """Get the next terminal terminal terminal from the input buffer. If 'ignore'
        is set to False, don't ignore white spaces characters and character
        that are not in the alphabet."""

        self.index = self.index + 1
        if self.index > len(self.input) - 1:
            self.end_reached = True
            return ""
        elif ignore and self.input[self.index] in " \f\n\r\t\v":
            return self.next_terminal() # ignore white spaces
        else:
            next_terminal = self.input[self.index]
            # ignore if nex_terminal not in alphabet or not in reserved 
            if (ignore and (next_terminal not in self.alphabet) and
                (next_terminal not in self.reserved)): 
                self.errors.append("error: '" + next_terminal + "' not in alphabet")
                return ""
            else:
                return next_terminal

    def get_definition(self):
        """Get the regular expression represented by the definition
        between the ocurrence of '[' and the first ']'. The name of
        the definition is added to the def_output for future use to
        draw the nfa representation of the definitions.
        """

        # Get the name of the definition, don't ignore white spaces and
        # characters that are not in the alphabet
        self.match('[')
        key = ""
        while (self.lookahead != ']'):
            key = key + self.lookahead
            self.lookahead = self.next_terminal(ignore=False)
        self.match("]")

        if key not in self.definitions:
            self.errors.append("error: '" + key + "' is not defined.")
            return ""

        self.def_output.append(key) # add to draw a nfa
        return self.definitions[key][0]

    def output(self, terminal):
        """Adds a terminal to the exp_output buffer."""

        self.exp_output = self.exp_output + terminal
        # If terminal length is > 1, then is an expresion obtained from the
        # definitions dict in the get_definition() function, the name of the
        # definition was already added to the definitions output there so we
        # don't have to add anything to the definitions output here.
        if len(terminal) == 1:
            # Add to the definitions output if terminal is a single character
            self.def_output.append(terminal)

    def match(self, terminal):
        """Matches the next terminal of the input buffer."""

        if (self.lookahead == terminal):
            # If terminal is '[', set ignore flag of next_terminal to False so
            # that no white spaces or characters that are not in the alphabet
            # will be ignored.
            self.lookahead = self.next_terminal(terminal != '[')
        else:
            self.errors.append("sintax error", self.lookahead)

    def exp0(self):
        """
        exp0 -> term0 exp1
        """

        self.term0(); self.exp1()

    def exp1(self):
        """
        exp1 -> '|' term0 {print '|'} exp1
              | empty
        """

        if self.lookahead == '|':
            self.match('|'); self.term0(); self.output('|'); self.exp1()
        else:
            return

    def term0(self):
        """
        term0 -> fact0 term1
        """

        self.fact0(); self.term1()

    def term1(self):
        """
        term1 -> '.' fact0 {print '.'} term1
               | fact0 {print '.'} term1
               | empty
        """

        if self.lookahead == '.':
            self.match('.'); self.fact0(); self.output('.'); self.term1()
        elif self.lookahead in self.alphabet + ['(', '[']:
            self.fact0(); self.output('.'); self.term1()
        else:
            return

    def fact0(self):
        """
        fact0 -> '(' exp0 ')' fact1
               | '[' get_definition ']' fact1
               | 'a in C' {print 'a'} fact1
        """

        if self.lookahead == '(':
            self.match('('); self.exp0(); self.match(')'); self.fact1()
        elif self.lookahead == '[':
            self.output(self.get_definition()); self.fact1()
        elif self.lookahead in self.alphabet:
            a = self.lookahead
            self.match(a); self.output(a); self.fact1()

    def fact1(self):
        """
        fact1 -> '*' {print '*'} fact1
               | '+' {print '+'} fact1
               | '?' {print '?'} fact1
        """

        if self.lookahead == '*':
            self.match('*'); self.output('*'); self.fact1()
        elif self.lookahead == '+':
            self.match('+'); self.output('+'); self.fact1()
        elif self.lookahead == '?':
            self.match('?'); self.output('?'); self.fact1()
        else:
            return

    def draw(self, filename=""):
        """Uses RegexToNFA to translate each defined name into a nfa
        and draws the nfa."""

        t = RegexToNFA()
        images = []

        t.alphabet = self.alphabet + self.definitions.keys()
        for key in self.definitions.keys():
            t.exp = self.definitions[key][1]
            image_filename = filename + "." + key
            t.traslate().draw(image_filename)
            images.append((key, image_filename))

        return images

class Stack:
    """Defines the operations over a stack."""

    def __init__(self) :
        self.items = []

    def push(self, item) :
        """Push item into this stack."""

        self.items.append(item)

    def pop(self) :
        """Pop item from this stack."""

        return self.items.pop()

    def isEmpty(self) :
        """Returns True if this stack is empty."""

        return (self.items == [])

class RegexToNFA:
    """An implementation Thompson's algorithm to translate a regular
    expression from postfix notation to its corresponding NFA.

    The suported operations are concatenation ('.'), alternation ('|'),
    zero or more repetitions ('*'), one or more repetitions ('+') and
    cero or one repetetions ('?').
    """

    def __init__(self, exp="", alphabet=[]):
        self.alphabet = []
        # add special characters to alphabet
        for literal in alphabet:
            self.alphabet.append(literal)
        if "ε" not in self.alphabet:
            self.alphabet.append("ε")
        # exp can be any iterable in postfix notation
        self.exp = exp

    def traslate(self):
        """Executes the translation from the input postfix regular expression
        to its corresponding NFA."""

        if "ε" not in self.alphabet:
            self.alphabet.append("ε")

        stack = Stack()
        for token in self.exp:
            if token == '.':
                nfa2 = stack.pop()
                nfa1 = stack.pop()
                nfa = self.concatenate(nfa1, nfa2)
                stack.push(nfa)
            elif token == '|':
                nfa2 = stack.pop()
                nfa1 = stack.pop()
                nfa = self.alternate(nfa1, nfa2)
                stack.push(nfa)
            elif token == '*':
                nfa1 = stack.pop()
                nfa = self.zero_or_more(nfa1)
                stack.push(nfa)
            elif token == '+':
                nfa1 = stack.pop()
                nfa = self.one_or_more(nfa1)
                stack.push(nfa)
            elif token == '?':
                nfa1 = stack.pop()
                nfa = self.zero_or_one(nfa1)
                stack.push(nfa)
            else:
                nfa = self.literal(token)
                stack.push(nfa)
        self.nfa = stack.pop()

        return self.nfa

    def concatenate(self, nfa1, nfa2):
        """Returns a nfa with the concatenation of nfa1 and nfa2."""

        final = len(nfa1.states) + len(nfa2.states) - 2
        nfa = NFA(0, final, [], self.alphabet)

        for state0 in nfa1.states:
            for char in self.alphabet:
                for state1 in nfa1.next_states(state0, char):
                    nfa.add_transition(state0, state1, char)

        extra_index = len(nfa1.states) - 1

        for state0 in nfa2.states:
            for char in self.alphabet:
                for state1 in nfa2.next_states(state0, char):
                    nfa.add_transition(state0 + extra_index,
                                       state1 + extra_index, char)

        return nfa

    def alternate(self, nfa1, nfa2):
        """Returns a nfa with the alternation of nfa1 and nfa2."""

        final = len(nfa1.states) + len(nfa2.states) + 1
        nfa = NFA(0, final, [0], self.alphabet)

        extra_index = 1
        nfa.add_transition(0, extra_index, "ε")

        for state0 in nfa1.states:
            for char in self.alphabet:
                for state1 in nfa1.next_states(state0, char):
                    nfa.add_transition(state0 + extra_index,
                                       state1 + extra_index, char)

        extra_index = 1 + len(nfa1.states)
        nfa.add_transition(0, extra_index, "ε")

        for state0 in nfa2.states:
            for char in self.alphabet:
                for state1 in nfa2.next_states(state0, char):
                    nfa.add_transition(state0 + extra_index,
                                       state1 + extra_index, char)

        nfa.add_transition(nfa1.final + 1, final, "ε")
        nfa.add_transition(nfa2.final + extra_index, final, "ε")

        return nfa

    def zero_or_more(self, nfa1):
        """Returns a nfa whit zero or more repetitions ('*') of nfa1."""

        final = len(nfa1.states) + 1
        nfa = NFA(0, final, [0], self.alphabet)

        extra_index = 1
        nfa.add_transition(0, extra_index, "ε")

        for state0 in nfa1.states:
            for char in self.alphabet:
                for state1 in nfa1.next_states(state0, char):
                    nfa.add_transition(state0 + extra_index,
                                       state1 + extra_index, char)

        nfa.add_transition(nfa1.final + extra_index,
                           nfa1.initial + extra_index, "ε")
        nfa.add_transition(nfa1.final + extra_index, final, "ε")
        nfa.add_transition(0, final, "ε")

        return nfa

    def one_or_more(self, nfa1):
        """Returns a nfa whit one or more repetitions ('+') of nfa1."""

        final = len(nfa1.states) + 1
        nfa = NFA(0, final, [0], self.alphabet)

        extra_index = 1
        nfa.add_transition(0, extra_index, "ε")

        for state0 in nfa1.states:
            for char in self.alphabet:
                for state1 in nfa1.next_states(state0, char):
                    nfa.add_transition(state0 + extra_index,
                                       state1 + extra_index, char)

        nfa.add_transition(nfa1.final + extra_index,
                           nfa1.initial + extra_index, "ε")
        nfa.add_transition(nfa1.final + extra_index, final, "ε")

        return nfa

    def zero_or_one(self, nfa1):
        """Returns a nfa whit zero or one repetitions ('?') of nfa1."""

        final = len(nfa1.states) + 1
        nfa = NFA(0, final, [0], self.alphabet)

        extra_index = 1
        nfa.add_transition(0, extra_index, "ε")

        for state0 in nfa1.states:
            for char in self.alphabet:
                for state1 in nfa1.next_states(state0, char):
                    nfa.add_transition(state0 + extra_index,
                                       state1 + extra_index, char)

        nfa.add_transition(nfa1.final + 1, final, "ε")
        nfa.add_transition(0, final, "ε")

        return nfa

    def literal(self, literal):
        """Returns a nfa that represents the literal character."""

        nfa = NFA(0, 1, [0], self.alphabet)
        nfa.add_transition(0, 1, literal)

        return nfa

class NFAtoDFA:

#    def convertNFAtoDFA(self, N):
#        """Converts the input NFA into a DFA.
#
#        The output DFA has a state for every *reachable* subset of states in
#        the input NFA. In the worst case, there will be an exponential
#        increase in the number of states.
#        """
#
#        q0 = frozenset(self.e_clousure(N, [N.initial]))
#        Q = set([q0])
#        unprocessedQ = Stack()
#        unprocessedQ.push(q0)
#        dfa = DFA(q0, [], [q0], N.alphabet)
#
#        while not unprocessedQ.isEmpty():
#            qSet = unprocessedQ.pop()
#            for literal in dfa.alphabet:
#                nextStates = self.e_clousure(N, self.move(N, qSet, literal))
#                if len(nextStates) > 0:
#                    nextStates = frozenset(nextStates)
#                    if not nextStates in Q:
#                        Q.add(nextStates)
#                        dfa.add_transition(qSet, nextStates, literal)
#                        unprocessedQ.push(nextStates)
#                        if N.final in nextStates:
#                            dfa.final.add(nextStates)
#                    else:
#                        dfa.add_transition(qSet, nextStates, literal)
#
#        dfa2 = DFA(0, [], [], N.alphabet)
#        for state in dfa.states:
#            dfa2.add_state(dfa.states.index(state))
#
#        for state in dfa.final:
#            dfa2.final.add(dfa.states.index(state))
#
#        dfa2.transitions = dfa.transitions
#
#        return dfa2
    
    def convert(self, N):
        """An implementation of the Subset Construction algorithm to convert a
        NFA into a DFA."""
        
        nfa = N
        dfa = DFA(initial=0, final=[], states=[], alphabet=nfa.alphabet)
        Dstates = Stack() # unprocessed states
        marked = []       # processed states
        
        # initially, e-closure(nfa.initial) is the only state in Dstates, 
        # and it is unmarked (only unmarked states are pushed into Dstates)
        Dstates.push(self.e_clousure(nfa, [nfa.initial]))
        
        # while there is an unmarked state T in Dstates ( if T is in Dstates, 
        # then it is unmarked)
        while not Dstates.isEmpty():
            T = Dstates.pop()
            marked.append(T) # mark T
            for char in dfa.alphabet:
                # U = e-closure(move(T,char))
                U = self.e_clousure(nfa, self.move(nfa, T, char))
                # if U is not in Dstates, add U as an unmarked state to it
                if U not in Dstates.items and not U in marked:
                    Dstates.push(U)
                # Dtran[T, char] = U
                dfa.add_transition(T, U, char)
                
        # now we create a new dfa wich states will be integers instead of
        # arrays.
        dfa2 = DFA(initial=0, final=[], states=[], alphabet=nfa.alphabet)
        
        for state in dfa.states:
            # for each array in dfa.states, add a state i in dfa2 where i is
            # the index of the array on dfa.states
            i = dfa.states.index(state)
            dfa2.add_state(i)
            # for each item in the array, check if it is a final state, if
            # so add i to the final states of dfa2
            for s in state:
                if s == nfa.final and not i in dfa2.final:
                    dfa2.final.append(i)

        # copy the transitions table. This works because every entry on the 
        # transitions table points to the index of the next state instead of 
        # pointing to the next state itself
        dfa2.transitions = dfa.transitions

        return dfa2

    def move(self, nfa, states, literal):
        """Return the set of states that can be reached form a set of states
        whit the character literal."""

        next_states = []
        for t in states:
            for u in nfa.next_states(t, literal):
                if u not in next_states:
                    next_states.append(u)

        next_states.sort()
        return next_states

    def e_clousure(self, nfa, T):
        """Calculates the empty clousure for a set T of states"""

        # push all states of T onto stack
        stack = Stack()
        for state in T:
            stack.push(state)

        # initialize e-closure(T) to T;
        clousure = T[::]

        # for each state u with an edge from t to u labeled e )
        while not stack.isEmpty():
            t = stack.pop()
            for u in nfa.next_states(t, "ε"):
                if u not in clousure:
                    clousure.append(u)
                    stack.push(u)

        clousure.sort()
        return clousure

class MinimizeDFA:

    def remove_dead(self, N):
        """Removes all states that don't have outer transitions"""

        dfa = N
        alive = set([dfa.initial])
        for state in dfa.final:
            alive.add(state)

        for state in dfa.states:
            if not state in alive and not state in dfa.final:
                for transition in dfa.transitions[dfa.states.index(state)]:
                    if transition >= 0:
                        alive.add(state)
                        break

        for state in dfa.states:
            if not state in alive:
                dfa.remove_state(state)

        return dfa

    def remove_inac(self, N):
        """Removes all the unreachable states"""

        dfa = N
        activeStates = set([dfa.initial])
        stack = Stack()
        stack.push(dfa.initial)

        while not stack.isEmpty():
            state = stack.pop()

            for literal in dfa.alphabet:
                transition = dfa.next_state(state, literal)
                if transition >= 0:
                    if not transition in activeStates:
                        activeStates.add(transition)
                        stack.push(transition)

        for state in dfa.states:
            if not state in activeStates:
                dfa.remove_state(state)


        return dfa

#    def minimize(self, N):
#        """Uses Hopcroft's Algorithm to minimize a DFA"""
#
#        dfa = N
#        final = []
#        for state in dfa.final:
#            final.append(state)
#
#        non_final = []
#        for state in dfa.states:
#            if not state in final:
#                non_final.append(state)
#
#        non_final.sort()
#
#        P = [final, non_final]
#        P.sort()
#
#        L = Stack()
#        L.push(non_final)
#
#        while not L.isEmpty():
#            S = L.pop()
#            for literal in dfa.alphabet:
#                for B in P:
#                    C = self.split(N, B, S, literal)
#                    if len(C[0]) != 0 and len(C[1]) != 0:
#                        C[0] = C[0]
#                        C[1] = C[1]
#                        P.remove(B)
#                        P.append(C[0])
#                        P.append(C[1])
#                        if len(C[0]) < len(C[1]):
#                            L.push(C[0])
#                        else:
#                            L.push(C[1])
#
#        dfa = DFA(0, [], [], N.alphabet)
#
#        #Adds the states in P into the DFA and selects the initial and final states
#        for state in P:
#            index = P.index(state)
#            dfa.add_state(index)
#            if N.initial in state:
#                dfa.initial = index
#            else:
#                for S in N.final:
#                    if S in state:
#                        dfa.final.add(index)
#                        break
#
#        #Copy the DFA into another DFA to change the names of the states into numbers
#        for state in dfa.states:
#            for literal in N.alphabet:
#                j = N.alphabet.index(literal)
#                transition = N.transitions[P[state][0]][j]
#                if transition >= 0:
#                    for S in P:
#                        if transition in S:
#                            dfa.add_transition(state, P.index(S), literal)
#
#        #Removes dead and unreachable states
#        #dfa = self.remove_dead(dfa)
#        #dfa = self.remove_inac(dfa)
#
#        return dfa
    
    def minimize(self, N):
        
        dfa = N
        
        # initialize P whit two sets, one for the final states and one for
        # the non-final states
        finals = []
        non_finals = []
        for state in dfa.states:
            if state in dfa.final:
                finals.append(state)
            else:
                non_finals.append(state)    
        P = [non_finals, finals]
        
        # initially, let Pnew = P
        Pnew = P[::]
        
        # flag to indicate if the partitioning is finished
        finished = False
        
        while not finished:
            for G in P:
                # partition G into subgroups
                Q = self.partition(dfa, G, P)
                # replace G in Pnew by the set of all subgroups formed
                Pnew.remove(G)
                for group in Q:
                    Pnew.append(group)
            # if Pnew = P, let Pfinal = P and continue with next step. Otherwise, 
            # repeat partitioning with Pnew in place of P
            if P == Pnew:
                finished = True
                Pfinal = P[::]
            else:
                P = Pnew[::]
        
        # choose one state (the first state in this case) in each group of Pfinal 
        # as the representative for that group
        representatives = []        
        for G in Pfinal:
            representatives.append(G[0])
        
        # select the new initial state
        initial = 0
        for state in representatives:
            if state == dfa.initial:
                initial = dfa.initial
                break
        
        # select the new final states
        final = []
        for state in representatives:
            if state in dfa.final:
                final.append(state)
        
        # add transitions
        dfa2 = DFA(initial=initial, final=final, states=[], alphabet=dfa.alphabet)
        for state0 in representatives:
            for char in dfa.alphabet:
                state1 = dfa.next_state(state0, char)
                for G in P:
                    if state1 in G:
                        representative = G[0]
                        dfa2.add_transition(state0, representative, char)

        return dfa2
                
    def partition(self, dfa, G, P):
        """Partition G into subgroups such that two states s and t are in the 
        same subgroup if and only if for all input symbols a, states s and t 
        have transitions on a to states in the same group of P."""
        
        # Calculate to wich group belongs each state.
        groups = {}
        for i in range(len(P)):
            for state in P[i]:
                groups[state] = i
        
        # Global transitions matrix. Each row is a vector of next gruop numbers
        # for every input in the alphabet.
        T = []
        
        # New gruops matrix. Each row is a vector of states with the same
        # next gruop vector. For example, if T[i] = [0,1], Q[i] = [st1, st2]
        # and alphabet = ['a', 'b'], then: 
        #   nfa.next_state(st1,'a') = x1 where x1 belong to group 0,
        #   nfa.next_state(st1,'b') = x2 where x2 belong to group 1,
        #   nfa.next_state(st2,'a') = y1 where x1 belong to group 0,
        #   nfa.next_state(st2,'b') = y2 where x2 belong to group 1,
        # wich means that st1 and st2 are in the same gruop.   
        Q = []
        
        # For each state in G, calculate its next group numbers vector
        for state0 in G:
            transitions = []
            for char in dfa.alphabet:
                state1 = dfa.next_state(state0, char)
                if state1 in groups:
                    transitions.append(groups[state1])
            # If the vector is not yet in T, append it
            if not transitions in T:
                T.append(transitions)
                Q.append([])
            # Append state0 to its corresponding group
            Q[T.index(transitions)].append(state0)

        return Q

#    def split(self, N, B, S, literal):
#        """Returns an array of two sets of states, the first one contents the intersection
#        between B and the states unreachable from S with literal, the second contents the
#        intersection between B and the reachable states from S with literal"""
#
#        states = []
#        for state in S:
#            move = N.next_state(state, literal)
#            if not move in states:
#                states.append(move)
#
#        B1 = []
#        B2 = []
#        for state in N.states:
#            if state in B:
#                if not state in states:
#                    B1.append(state)
#                else:
#                    B2.append(state)
#        B1.sort()
#        B2.sort()
#        result = [B1, B2]
#        return result

class DFAtoBNF:

    def convert(self, dfa):
        """Converts a DFA into a BNF"""

        result = BNF()
        #For each States add a Non Terminal symbol
        for state in dfa.states:
            result.add_non_terminal("N" + str(state))

        #For each transition A(j) -> A1 adds a production of the type A-> jA1
        for state0 in dfa.states:
            for char in dfa.alphabet:
                state1 = dfa.next_state(state0, char)
                if state1 >= 0:
                    result.add_production("N" + str(state0), char + "N" + str(state1))

        #For each state in final states adds a transition of type A -> ε
        for state in dfa.final:
            result.add_production("N" + str(state), "ε")

        #Set the initial state as the initial symbol of the grammar
        result.set_initial_symbol("N" + str(dfa.initial))

        return result
